//单链表

#pragma once

//单链表类型定义

template <typename E>
struct LNode
{
    E date;
    LNode *next;
};

template <typename E>
using LinkList = LNode<E> *;

//初始化空表
template <typename E>
void InitList(LinkList<E> &L)
{
    L = new LNode<E>;
    L->next = nullptr; // 0 , NULL
}

//销毁单链表 DestroyList(&L)
template <typename E>
void DestroyList(LinkList<E> &L)
{
    while (L)
    {
        auto P = L;
        L = L->next;
        delete P;
    }
}

//单链表插入  ListInsert(&L,i,e)
template <typename E>
void ListInsert(LinkList<E> &L, int i, E e)
{
    //找到第i-1个节点 p
    auto p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;j++;
    }
    //在p之后插入 e
    if (p && j == i - 1)
    {
        //auto s = new LNode<E>;
        //s->date = e;
        //s-nest = p ->nest;
        //p->next = s;
        p->next = new LNode<E> {e, p->next};
    }
    else
    {
        throw "i out of range";
    }
}

//单链表删除 ListDelete(&L,i,&e)
template <typename E>
void ListDelete(LinkList<E> &L, int i, E &e)
{
    //找到第i-1个节点 p
    auto p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }

    //删除第 i 个节点
    if (p && j == i - 1 && p->next)
    {
        auto q = p->next;
        p->next = q->next;
        e = q->date;
        delete q;
    }
    else
    {
        throw "i out of range";
    }
}

//单链表测试

#include <iostream>
#include "linklist.h"

using namespace std;

template <typename E>
void PrintList(LinkList<E> L)
{
    for (auto p = L->next; p; p = p->next)
        cout << p->date << " ";
    cout << endl;
}


int main()
{
    LinkList<int> L;
    InitList(L);

    ListInsert(L, 1, 1);
    ListInsert(L, 2, 2);
    ListInsert(L, 3, 3);
    ListInsert(L, 4, 4);
    ListInsert(L, 5, 5);

    PrintList(L);

    int e;
    ListDelete(L, 3, e);
    PrintList(L);

    return 0;
}